package com.kevin.Code.Array;

/**
 * @author Vinlee Xiao
 * @Classname Searcha2dMatrix
 * @Description Leetcode 74 搜索二维矩阵 中等难度 有思路
 * @Date 2021/10/31 15:36
 * @Version 1.0
 */
public class Searcha2dMatrix {

    /**
     * 每一层使用二维数组
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {

        int m = matrix.length;
        int n = matrix[0].length;

        if (m == 1 && n == 1) {

            return target == matrix[0][0];
        }

        //对每一行进行二分查找
        for (int i = 0; i < m; i++) {

            //进行二分查找
            int low = 0;
            int high = n - 1;
            while (low <= high) {
                int mid = (low + high) / 2;

                if (matrix[i][mid] == target) {
                    return true;
                } else if (matrix[i][mid] < target) {
                    low = mid + 1;
                } else if (matrix[i][mid] > target) {
                    high = mid - 1;
                }
            }
        }

        return false;
    }
}
